1. Field of the Invention
The present invention relates to distributed processing system and method for discrete logarithm calculation, and more particularly, to distributed processing system and method for discrete logarithm calculation, capable of improving the speed and resource efficiency of the discrete logarithm calculation by allowing a plurality of operation agents to distributively process a discrete logarithm calculation operation using a pre-calculation table.
2. Description of the Related Art
A discrete logarithm problem is defined within a cyclic group regarding multiplication which is formed in a finite ring having N as a group order, is a problem for, when a generator of the cyclic group is g, searching for k that satisfies y=g^k mod N with respect to a given number (target element) y from among elements of the cyclic group, and may be broadly used in a public key encryption system, etc.
From among methods of solving the discrete logarithm problem, a discrete logarithm calculation method using a pre-calculation table is also referred to as a trapdoor discrete logarithm (TDL) and an operation of generating the pre-calculation table is referred to as chain generation. In the TDL, operations of generating a pre-calculation table and calculating a discrete logarithm are as described below.
Initially, with respect to a discrete logarithm problem, a group order N of a ring may be set as represented in Equation 1.N=pq(p-1 and q-1 are multiples of a certain number of prime factors having sizes of B-smooth numbers and a certain number of prime factors having sizes equal to or less than B/2-smooth numbers)  [Equation 1]
Here, B is generally set as a number equal to or greater than 80 in consideration of a cryptological stability.
If the prime factors are set as described above, sub-groups using the prime factors as group orders may be defined. In this case, a generator of each sub-group is referred to as a sub-generator.
A pre-calculation table may be generated with respect to a sub-generator of a sub-group corresponding to each prime factor. The pre-calculation table is a table for storing exponents and function values obtained by applying an iterated function such as an r-adding walk to a certain number of initial values having the sub-generator as a base and having different arbitrary exponents, and may be generated with respect to each prime factor.
A discrete logarithm problem with respect to the given number (target element) y from among elements of the cyclic group may be divided into a plurality of small discrete logarithm problems. If a given number in the divided small discrete logarithm problem is y′, in order to solve a small discrete logarithm problem, an operation of applying an iterated function such as an r-adding walk to a value having y′ as a base and having an arbitrary exponent is necessary.
In the operation of applying the iterated function, a small discrete logarithm problem may use a pre-calculation table generated with respect to a corresponding prime factor. If a value obtained when the iterated function is applied in an operation of solving a discrete logarithm problem equals to a function value in the pre-calculation table, the efficiency of overall operations may be increased by using previously calculated information in the pre-calculation table.
Also, in operations of generating a pre-calculation table and calculating a discrete logarithm with respect to a given number, an iterated function based on modulo multiplication has to be continuously used and, in order to promote the modulo multiplication, result values of modulo multiplication using a sub-generator of a sub-group corresponding to each prime factor may be previously calculated and stored in a table that is called as a modulo multiplication auxiliary table.
A representative algorithm related to promotion of an iterated function based on modulo multiplication using a modulo multiplication auxiliary table is, but not limited to, tag tracing.
As described above, conventionally, when a discrete logarithm problem required to issue an encryption key is calculated, attempts have been made to increase the efficiency of calculation by using tag tracing or a pre-calculation table. However, even when a method using tag tracing or a pre-calculation table is applied, quite large operation time and storage space are still required and thus a large number of encryption key issuing requests may not be easily and simultaneously processed.
Accordingly, a technology for increasing the efficiency of calculation not in terms of an algorithm but in terms of a system, for example, distributed processing, is demanded.